package leetcode.median;

import java.util.List;

/**
 * ClassName: $139_WordBreak
 * Description: 单词拆分
 * date: 2022-01-28 19:26
 *
 * @author liyifan
 */
public class $139_WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 递归会超时
        return recur(s, wordDict);
    }

    public boolean recur(String s, List<String> wordDict) {
        if (s.length() == 0)
            return true;

        boolean res = false;
        for (String temp:wordDict) {
            if (s.startsWith(temp)) {
                res = res || recur(s.substring(temp.length()), wordDict);
            }
            if (res)
                break;
        }
        return res;
    }

    public boolean wordBreakDP(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 0;i < s.length();i++) {
            for (int j = i + 1;j <= s.length();j++) {
                if (dp[i] && wordDict.contains(s.substring(i, j))) {
                    dp[j] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
